1. Field of the Invention
The present invention relates to an array compression system for reducing the size of the array used in processing a large amount of data, that is, the number of elements of arrays, in a program.
2. Description of the Related Art
To efficiently execute a numerical calculation program, etc. which processes a large amount of data, it is necessary to effectively use cache, etc. To attain this, various methods have been suggested. An array compression method is one of the methods, and is an optimizing method by reducing the size of an array and improving the locality.
Before explaining the compression of an array, the terms relating to the arrays used in the present invention are described below. FIG. 1 is an explanatory view of an example of a loop nest sequence which is a sequence of loop nests. FIG. 1 shows the loop nest of an array A including leading subscripts I and J.
The loop nest takes on a nest structure having an outside loop relating to the subscript J and an inside loop relating to the subscript I. However, in the explanation below, even though there is no nested structure, it is still referred to as a loop nest.
Described below is the locality of an array. First, that an array A is local in an area R means that the elements of A defined or referenced in the area R are all local in the area R. An area is an arbitrary part of an entire program. Each of a loop nest and a loop nest sequence is an area.
Additionally, that an element e of the array A is local in the area R means that the first condition that the value of e referenced in the area R is necessarily defined in the area R before the reference, and that the second condition that the value of e defined in the area R is necessarily referenced only in the area R are satisfied.
FIG. 2 shows the conventional technology of array compression. In FIG. 2, a one-dimensional array T (I) is defined in the upper portion, and then the array A (I) is defined with the array T (I) referenced. If the contents of the array T (I) are not referenced in another area of the entire program, then the array formed by N elements from T (1) to T (N) can be described as a scalar variable T as shown in the lower portion of FIG. 2, and the size of the array can be reduced.
The above-mentioned conventional technology of array compression is described in the document relating to the technology of G. R. Gao et al, “Collective Loop Fusion For Array Contraction”, ACAPS Technical Memo 41, Mcgill Univ. 1992, etc.